# https://leetcode-cn.com/problems/omKAoA/
# 剑指 Offer II 094. 最少回文分割
# 给定一个字符串 s，请将 s 分割成一些子串，使每个子串都是回文串。
#
# 返回符合要求的 最少分割次数 。
#
#
#
# 示例 1：
#
# 输入：s = "aab"
# 输出：1
# 解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
# 示例 2：
#
# 输入：s = "a"
# 输出：0
# 示例 3：
#
# 输入：s = "ab"
# 输出：1
#
#
# 提示：
#
# 1 <= s.length <= 2000
# s 仅由小写英文字母组成
#
# 题解:
# if s[0:i+1]是回文字符串: d[i] = 0
# else: d[i] = min([d[j] for j in range(i) if s[j:i]是回文])+1
#
# s = 'aabc'
# d[0] = 0
# d[1] = 0
# d[2] = d[1] + 1 = 1, s[2:3] = 'b'是回文
# d[3] = d[2] + 1= 3, s[3,4]='c'是回文
class Solution:
    def minCut(self, s: str) -> int:
        pass


